import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: wlx
 * Date: 2025-06-22
 * Time: 0:40
 */
public class quickSort {
    public static void quickSort(int[] num) {
        int left = 0;
        int right = num.length-1;
        quick(num,left,right);
    }


    public static void quick(int[] num, int left, int right) {
        if(left >= right) {
            return;
        }
        // 基准值优化
        int index = midThree(num,left,right);
        swap(num,index,left);

        int pivot = partition(num,left,right);
        quick(num,left,pivot-1);
        quick(num,pivot+1,right);
    }

    private static int midThree(int[] array,int left,int right) {
        int mid = (left + right) / 2;
        if (array[left] < array[right]) {
            if (array[mid] < array[left]) {
                return left;
            } else if (array[mid] > array[right]) {
                return right;
            } else {
                return mid;
            }
        } else {
            if (array[mid] < array[right]) {
                return right;
            } else if (array[mid] > array[left]) {
                return left;
            } else {
                return mid;
            }
        }
    }

    public static int partition(int[] arr,int left,int right) {
        int tmp = arr[left];

        while(left < right) {
            // 找到比基准tmp小的
            while(left < right && arr[right] >= tmp) {
                right--;
            }
            arr[left] = arr[right];
            // 找到比基准tmp大的
            while(left < right && arr[left] <= tmp) {
                left++;
            }
            arr[right] = arr[left];
        }
        arr[left] = tmp;
        return left;
    }



    public static void swap(int[] arr,int i,int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static void main(String[] args) {
        int[] array = {1,4,2,9,6,7};
        quickSort(array);
        System.out.println(Arrays.toString(array));
    }
}
